TNotes.leetcode

Appearance

0036. 有效的数独【中等】

0036. 有效的数独【中等】 ​

1. 📝 题目描述 ​

请你判断一个 9 x 9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

注意：

  • 一个有效的数独（部分已被填充）不一定是可解的。
  • 只需要根据以上规则，验证已经填入的数字是否有效即可。
  • 空白格用 '.' 表示。

示例 1：

img

txt
输入：board = [
  ["5", "3", ".", ".", "7", ".", ".", ".", "."],
  ["6", ".", ".", "1", "9", "5", ".", ".", "."],
  [".", "9", "8", ".", ".", ".", ".", "6", "."],
  ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
  ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
  ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
  [".", "6", ".", ".", ".", ".", "2", "8", "."],
  [".", ".", ".", "4", "1", "9", ".", ".", "5"],
  [".", ".", ".", ".", "8", ".", ".", "7", "9"]
]
输出：true

示例 2：

txt
输入：board = [
  ["8", "3", ".", ".", "7", ".", ".", ".", "."],
  ["6", ".", ".", "1", "9", "5", ".", ".", "."],
  [".", "9", "8", ".", ".", ".", ".", "6", "."],
  ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
  ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
  ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
  [".", "6", ".", ".", ".", ".", "2", "8", "."],
  [".", ".", ".", "4", "1", "9", ".", ".", "5"],
  [".", ".", ".", ".", "8", ".", ".", "7", "9"]
]
输出：false

解释：

  • 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与示例1相同。
  • 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

提示：

  • board.length == 9
  • board[i].length == 9
  • board[i][j] 是一位数字（1-9）或者 '.'

2. 🎯 s.1 - 一次遍历 + 位掩码 ​

c
bool isValidSudoku(char** board, int boardSize, int* boardColSize) {
    // rows[i] / cols[j] / boxes[k] 分别用位运算记录数字出现情况
    int rows[9] = {0}, cols[9] = {0}, boxes[9] = {0};

    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] == '.')
                continue;
            int num = board[i][j] - '0'; // 1~9
            int bit = 1 << num;
            int boxIdx = (i / 3) * 3 + j / 3;

            if (rows[i] & bit || cols[j] & bit || boxes[boxIdx] & bit)
                return false;
            rows[i] |= bit;
            cols[j] |= bit;
            boxes[boxIdx] |= bit;
        }
    }
    return true;
}
js
/**
 * @param {character[][]} board
 * @return {boolean}
 */
var isValidSudoku = function (board) {
  // rows[i] / cols[j] / boxes[k] 分别用位运算记录数字出现情况
  const rows = Array.from({ length: 9 }, () => 0)
  const cols = Array.from({ length: 9 }, () => 0)
  const boxes = Array.from({ length: 9 }, () => 0)

  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      if (board[i][j] === '.') continue
      const num = board[i][j] - '0' // 1~9
      const bit = 1 << num
      const boxIdx = Math.floor(i / 3) * 3 + Math.floor(j / 3)

      if (rows[i] & bit || cols[j] & bit || boxes[boxIdx] & bit) return false
      rows[i] |= bit
      cols[j] |= bit
      boxes[boxIdx] |= bit
    }
  }
  return true
}
py
class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        # rows[i] / cols[j] / boxes[k] 分别用位运算记录数字出现情况
        rows = [0] * 9
        cols = [0] * 9
        boxes = [0] * 9

        for i in range(9):
            for j in range(9):
                if board[i][j] == ".":
                    continue
                num = int(board[i][j])  # 1~9
                bit = 1 << num
                box_idx = (i // 3) * 3 + j // 3

                if rows[i] & bit or cols[j] & bit or boxes[box_idx] & bit:
                    return False
                rows[i] |= bit
                cols[j] |= bit
                boxes[box_idx] |= bit

        return True
  • 时间复杂度：O(1)，棋盘固定为 9×9=81 格，遍历次数是常数
  • 空间复杂度：O(1)，三组长度为 9 的整型数组均为常数大小

算法思路：

  • 用三组长度为 9 的整数数组 rows、cols、boxes 分别记录每行、每列、每宫内数字的出现状态，第 num 位为 1 表示该数字已出现
  • 对每个非空格计算：
    • bit = 1 << num：每个数字对应唯一的一个位
    • boxIdx = (i/3)*3 + j/3：该数字所属的宫格 ID
  • 依据 bit 来判断：
    • 若当前行、列、宫任一掩码中该位已置 1，则返回 false
    • 否则同时对三个掩码置位

Discussions